#include <iostream>
#include <stdexcept>
#include <vector>

int lcs_bottomup(const std::vector<int> & x, 
				 const std::vector<int> & y, 
				 std::vector<std::vector<int> > & c, 
				 std::vector<std::vector<int> > & b) 
{
	c.resize(x.size()+1);
	b.resize(x.size()+1);
	for (unsigned int i =0; i < x.size()+1; i++ ) {
		c[i].resize(y.size()+1,-1);
		b[i].resize(y.size()+1,2);
	}
	for (unsigned int i = 0; i < x.size()+1; i++) {
		c[i][0] = 0;
	}
	for (unsigned int j = 0; j < y.size()+1; j++) {
		c[0][j] = 0;
	}

	for (unsigned int i=0; i < x.size(); i++) { //index of x, the corresponding index in c and b is i+1
		for (unsigned int j=0; j < y.size(); j++) { //index of y, the corresponding index in c and b is j+1
			if ( x[i] == y[j] ) {
				c[i+1][j+1] = c[i][j] + 1;
				b[i+1][j+1] = 0; // case 1;
			}
			else if ( c[i+1][j] >= c[i][j+1] ) {
				c[i+1][j+1] = c[i+1][j];
				b[i+1][j+1] = -1;
			}
			else {
				c[i+1][j+1] = c[i][j+1];
				b[i+1][j+1] = 1;
			}
		}
	}
	return c[x.size()][y.size()];
}

int lcs_recursive(const std::vector<int> & x, 
				  const std::vector<int> & y, 
				  std::vector<std::vector<int> > & c,
				  std::vector<std::vector<int> > & b,
				  int i, int j)
{
	if (c[i+1][j+1] >=0)
		return c[i+1][j+1];
	if (i < 0 || j < 0)
		return 0;
	if (x[i] == y[j]) {
		c[i+1][j+1] = c[i][j] + 1;
		b[i+1][j+1] = 0;
	}
	else {
		int p = lcs_recursive(x,y,c,b,i-1,j);
		int q = lcs_recursive(x,y,c,b,i,j-1);
		if (p >= q) {
			c[i+1][j+1] = p;
			b[i+1][j+1] = 1;
		}
		else {
			c[i+1][j+1] = q;
			b[i+1][j+1] = -1;
		}
	}
	return c[i+1][j+1];
}

int lcs_topdown(const std::vector<int> & x, 
				  const std::vector<int> & y, 
				  std::vector<std::vector<int> > & c,
				  std::vector<std::vector<int> > & b)
{
	c.resize(x.size()+1);
	b.resize(x.size()+1);
	for (unsigned int i =0; i < x.size()+1; i++ ) {
		c[i].resize(y.size()+1,-1);
		b[i].resize(y.size()+1,2);
	}
	return lcs_recursive(x,y,c,b,x.size()-1,y.size()-1);
}

void print_lcs (const std::vector<std::vector<int> > & b, const std::vector<int> & x, int i, int j) { // i,j are last indices of x, y
	if (i < 0 || j < 0)
		return;
	if (b[i+1][j+1] == 0) {
		print_lcs(b, x, i-1, j-1);
		std::cout << (char)x[i] << ' ';
	}
	else if (b[i+1][j+1] == 1)
		print_lcs(b,x,i-1,j);
	else if (b[i+1][j+1] == -1)
		print_lcs(b,x,i,j-1);
	else 
		throw std::logic_error("error in printing the lcs\n");
}

void print_lcs_with_c(const std::vector<std::vector<int> > & c, const std::vector<int> & x,
					  const std::vector<int> & y, int i, int j) { // i,j are last indices of x, y
	if (i < 0 || j < 0)
		return;
	if (x[i] == y[j] && c[i+1][j+1] == c[i][j]+1) {
		print_lcs_with_c(c, x, y, i-1, j-1);
		std::cout << (char)x[i] << ' ';
	}
	else if (c[i+1][j+1] == c[i+1][j])
		print_lcs_with_c(c,x,y,i,j-1);
	else if (c[i+1][j+1] == c[i][j+1])
		print_lcs_with_c(c,x,y,i-1,j);
	else 
		throw std::logic_error("error in printing the lcs\n");
}

int lcs_bottomup_compact(std::vector<int> & x,
						std::vector<int> & y,
						std::vector<std::vector<int> > & c)
{
	bool swapped = false;
	if (x.size() < y.size() ) { // make sure x.size >= y.size
		x.swap(y);
		swapped = true;
	}
	c.resize(2);
	for (int i=0; i<2; i++)
		c[i].resize(y.size()+1, -1);
	int prev = 0, curr = 1;
	for (unsigned int j = 0; j < c[prev].size(); j++)
		c[prev][j] = 0;
	for (unsigned int i = 0; i < x.size(); i++) {
		for (unsigned int j = 0; j < y.size(); j++) {
			if (x[i] == y[j])
				c[curr][j+1] = c[prev][j]+1;
			else if (c[curr][j] >= c[prev][j+1])
				c[curr][j+1] = c[curr][j];
			else
				c[curr][j+1] = c[prev][j+1];
		}
		prev = (prev+1)%2;
		curr = (curr+1)%2;
	}
	if (swapped == true) {
		x.swap(y);
		return c[prev][x.size()];
	}
	return c[prev][y.size()];
}

int lcs_bottomup_more_compact(std::vector<int> & x, std::vector<int> & y, std::vector<std::vector<int> > & c) {
	bool swapped = false;
	if (x.size() < y.size()) {
		x.swap(y);
		swapped = true;
	}
	int corner = 0;
	c.resize(1);
	c[0].resize(0);
	c[0].resize(y.size()+1, 0);
	for (int i = 0; i < x.size(); i++) {
		for (int j = 0; j < y.size(); j++) {
			if (x[i] == y[j]){
				int tmp = c[0][j+1];
				c[0][j+1] = corner + 1;
				corner = tmp;
			}
			else {
				corner = c[0][j+1];
				if ( c[0][j] >= c[0][j+1] )
					c[0][j+1] = c[0][j];
			}
		}
		corner = 0;
	}
	if (swapped) {
		x.swap(y);
		return c[0][x.size()];
	}
	return c[0][y.size()];
}

void test_lcs_internal(int * xa, int m, int * ya, int n)
{
	std::vector<int> x(xa, xa+m);
	std::vector<int> y(ya, ya+n);
	std::vector<std::vector<int> > c,b;
	
	std::cout << "the length of LCS(bottom-up) is " << lcs_bottomup(x,y,c,b) << std::endl;
	print_lcs(b, x, x.size()-1, y.size()-1); std::cout << std::endl;
	print_lcs_with_c(c, x, y, x.size()-1, y.size()-1); std::cout << std::endl;

	std::cout << "the length of LCS(top-down) is " << lcs_topdown(x,y,c,b) << std::endl;
	print_lcs(b, x, x.size()-1, y.size()-1); std::cout << std::endl;
	print_lcs_with_c(c, x, y, x.size()-1, y.size()-1); std::cout << std::endl;

	std::cout << "the length of LCS(bottom-up-compact) is " << lcs_bottomup_compact(x,y,c) << std::endl;
	std::cout << "the length of LCS(bottom-up-more-compact) is " << lcs_bottomup_more_compact(x,y,c) << std::endl;
}

void test_lcs() {
	int xa[] = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};
	int ya[] = {'B', 'D', 'C', 'A', 'B', 'A'};
	test_lcs_internal(xa, sizeof(xa)/sizeof(int), ya, sizeof(ya)/sizeof(int) );

	std::cout << "test 2 \n";
	int xa1[] = {'1', '0', '0', '1', '0', '1', '0', '1'};
	int ya1[] = {'0', '1', '0', '1', '1', '0', '1', '1', '0'};
	test_lcs_internal(xa1, sizeof(xa1)/sizeof(int), ya1, sizeof(ya1)/sizeof(int) );
}